//Alice 和 Bob 再次设计了一款新的石子游戏。现有一行 n 个石子，每个石子都有一个关联的数字表示它的价值。给你一个整数数组 stones ，其中 
//stones[i] 是第 i 个石子的价值。 
//
// Alice 和 Bob 轮流进行自己的回合，Alice 先手。每一回合，玩家需要从 stones 中移除任一石子。 
//
// 
// 如果玩家移除石子后，导致 所有已移除石子 的价值 总和 可以被 3 整除，那么该玩家就 输掉游戏 。 
// 如果不满足上一条，且移除后没有任何剩余的石子，那么 Bob 将会直接获胜（即便是在 Alice 的回合）。 
// 
//
// 假设两位玩家均采用 最佳 决策。如果 Alice 获胜，返回 true ；如果 Bob 获胜，返回 false 。 
//
// 
//
// 示例 1： 
//
// 
//输入：stones = [2,1]
//输出：true
//解释：游戏进行如下：
//- 回合 1：Alice 可以移除任意一个石子。
//- 回合 2：Bob 移除剩下的石子。 
//已移除的石子的值总和为 1 + 2 = 3 且可以被 3 整除。因此，Bob 输，Alice 获胜。
// 
//
// 示例 2： 
//
// 
//输入：stones = [2]
//输出：false
//解释：Alice 会移除唯一一个石子，已移除石子的值总和为 2 。 
//由于所有石子都已移除，且值总和无法被 3 整除，Bob 获胜。
// 
//
// 示例 3： 
//
// 
//输入：stones = [5,1,2,4,3]
//输出：false
//解释：Bob 总会获胜。其中一种可能的游戏进行方式如下：
//- 回合 1：Alice 可以移除值为 1 的第 2 个石子。已移除石子值总和为 1 。
//- 回合 2：Bob 可以移除值为 3 的第 5 个石子。已移除石子值总和为 = 1 + 3 = 4 。
//- 回合 3：Alices 可以移除值为 4 的第 4 个石子。已移除石子值总和为 = 1 + 3 + 4 = 8 。
//- 回合 4：Bob 可以移除值为 2 的第 3 个石子。已移除石子值总和为 = 1 + 3 + 4 + 2 = 10.
//- 回合 5：Alice 可以移除值为 5 的第 1 个石子。已移除石子值总和为 = 1 + 3 + 4 + 2 + 5 = 15.
//Alice 输掉游戏，因为已移除石子值总和（15）可以被 3 整除，Bob 获胜。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= stones.length <= 10⁵ 
// 1 <= stones[i] <= 10⁴ 
// 
// Related Topics 贪心 数组 数学 计数 博弈 👍 41 👎 0

package com.cute.leetcode.editor.cn;

public class StoneGameIx {
    public static void main(String[] args) {
        int[] stones = {1,1,7,10,8,17,10,20,2,10};
        new StoneGameIx().new Solution().stoneGameIX(stones);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 博弈问题要分情况进行讨论
         * A只有一种获胜方式，是使得 B在选石子时凑成3的倍数；
         * 将所有棋子都转换为0 1 2 三种数值，A先手，分情况进行讨论
         * 一：数值为0的棋子个数为偶数，相当于没有0棋子，即无法换手
         *      棋子1个数为0，此时A先手只能选2，B也只能选2，最终会交回到A手中凑成3的倍数，A必输
         *      棋子2个数为0，仍然是A必输
         *      棋子1和2都不为0的时候，A先手时B必然选和A一样的，如果没有一样的B输，如果有一样的下一轮A选择之后B还是被动，A必赢
         * 二：数值为0的棋子为奇数，可以理解为换手次数只有一次，双方共用此机会
         *      棋子1和2的个数差不超过2：
         *          两个棋子一样多时：A起手无法使用0棋子（会直接输），所以A只能选择1或者2，此时B使用0转移给A，B只需要不选择满3的棋子就能赢
         *          两个棋子不一样多时：A起手无论选择哪一个，B都直接换手到A，最终B也会赢
         *      棋子1和2的个数差超过2：
         *          此时A只要先手选择最多的时候，无论之后B换手还是A换手，A都可以通过换手或者另一个棋子抵消掉，最终A赢
         *
         */
        public boolean stoneGameIX(int[] stones) {
            int[] cnt = new int[3];
            for (int stone : stones) cnt[stone % 3]++;
            return cnt[0] % 2 == 0 ? !(cnt[1] == 0 || cnt[2] == 0) : !(Math.abs(cnt[1] - cnt[2]) <= 2);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}